import java.util.Arrays;

public class Solution1349 {
    public int maxStudents(char[][] seats) {
        int n=seats[0].length;
        int[] f=new int[1<<n];
        for (int i=0;i<1<<n;i++){
            if (valid(i,seats[0])){
                f[i]=Integer.bitCount(i);
            }
        }
        for (int i=1;i<seats.length;i++){
            int[] g=new int[1<<n];
            for (int j=0;j<1<<n;j++){
                if (valid(j,seats[i])){
                    for (int k=0;k<1<<n;k++){
                        if (valid(k,seats[i-1]) && valid2(j,k,n)){
                            g[j]=Math.max(g[j],f[k]+Integer.bitCount(j));
                        }
                    }
                }
            }
            f=g;
        }
        return Arrays.stream(f).max().getAsInt();
    }

    private boolean valid2(int x, int y,int n) {
        for (int i=0;i<n;i++){
            if (i-1>=0 && (x&(1<<i))>0 && (y&(1<<(i-1)))>0){
                return false;
            }
            if (i+1<n && (x&(1<<i))>0 && (y&(1<<(i+1)))>0){
                return false;
            }
        }
        return true;
    }

    private boolean valid(int k, char[] seat) {
        for (int i=0;i<seat.length;i++){
            if ((k&(1<<i))>0 && seat[i]=='#'){
                return false;
            }
        }
        for (int i=0;i<seat.length-1;i++){
            if ((k&(1<<i))>0 && (k&(1<<(i+1)))>0){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1349().maxStudents(new char[][]{{'#','.','#','#','.','#'},{'.','#','#','#','#','.'},{'#','.','#','#','.','#'}}));
    }
}
